package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/
 * @create 2025/10/22 20:08
 * @since JDK17
 */

public class Solution47 {
    int f(int[] col, int p) {
        int n = col.length, ans = 0;
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = i; j < n; j++) {
                sum += col[j];
                if (sum < p) {
                    ans = Math.max(ans, ((int) sum));
                }
            }
        }
        return ans;
    }
    public int maxSumSubmatrix(int[][] matrix, int p) {
        int n = matrix.length, m = matrix[0].length, ans = 0;
        for (int i = 0; i < n; i++) {
            int[] col = new int[m];
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    col[k] += matrix[j][k];
                }
                ans = Math.max(ans, f(col, p));
            }
        }

        return ans;
    }
}
